#define _CRT_SECURE_NO_WARNINGS

#include "HFtree.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"


// 比较函数，用于 qsort 排序
int compare(const void* a, const void* b) {
	return (*(int*)a - *(int*)b);
}

// 排序数组中的非零元素
void sort_non_zero(int arr[], int size) {
	int i = 0, nonZeroCount = 0;

	// 第一步：将所有非零元素移动到数组前面
	for (i = 0; i < size; i++) {
		if (arr[i] != 0) {
			arr[nonZeroCount++] = arr[i];
		}
	}

	// 第二步：对非零元素排序
	qsort(arr, nonZeroCount, sizeof(int), compare);

	// 第三步：将剩余的位置填充为0
	for (i = nonZeroCount; i < size; i++) {
		arr[i] = 0;
	}
}

//统计字符串每个字符出现的次数参考代码
//返回为int，用于确定树的叶子个数
int alphabet(char* str,int* count)
{
	int i = 0;
	int num = 0;
	int k = 0;
	for (i = 0; i < strlen(str); i++)
	{
		count[str[i] - 'a']++;
	}
	for (i = 0; i < 26; i++)
	{
		if (count[i] != 0)
		{
			printf("%c:%d ", i + 'a', count[i]);
			/*str[k] = i + 'a';
			k++;*/
			num++;
		}
	}
	printf("\n");
	return num;
}

//创建一片森林，每个树为空
HuffmanTree tree_Create(int n)//n个叶子结点
{
	int i = 0;
	int m = 2 * n - 1;
	HuffmanTree HFtree = (HuffmanTree)malloc(sizeof(HTNode) * m);
	for (i = 0; i < m; i++)
	{
		HFtree[i].lchild = 0;
		HFtree[i].parent = 0;
		HFtree[i].rchild = 0;
		HFtree[i].weight = 0;
	}
	return HFtree;
}

//对每一个树进行字母的权值赋值
//count是指向权值数组的指针
void tree_Voluate(HuffmanTree HFtree,int* count)
{
	int i = 0;
	int k = 0;
	int num = 0;
	int arr[26] = { 0 };
	for (i = 0; i < 26; i++)
	{
		if (count[i] != 0)
		{
			arr[k] = count[i];
			num++;
			k++;
		}
	}
	for (i = 0; i < num; i++)
	{
		HFtree[i].weight = arr[i];
	}
}

//对当前森林的头节点大小进行排序，并且将最小两个权值相加创建一个新的树
//x和y是最小权值的两个树的下标
void Str_Sort(HuffmanTree HFtree,int n,int* x,int* y,char* str,int* count)
{
	int i = 0;
	int j = 0;
	int m = n * 2 - 1;
	int arr[MAX_SIZE] = { 0 };
	for (i = 0; i < m; i++)
	{
		if (HFtree[i].parent == 0 && HFtree[i].weight != 0)//判断只有无双亲并且权值不为0才可以被记录数组
		{
			arr[j] = HFtree[i].weight;
			j++;
		}
	}
	sort_non_zero(arr, MAX_SIZE);//将权值数组进行从小到达排列
	for (i = 0; i < m; i++)
	{
		if (arr[0] == HFtree[i].weight && HFtree[i].parent == 0)//找到最小的无双亲的树
		{
			*x = i;
			int k = 0;
			for (k = 0; k < 26; k++)//将这个叶子的权值对应的ascll码值赋给str，用于解码
			{
				if (count[k] == HFtree[i].weight)//如果之前的count数组里面有等于这个叶子权值的，那么就说明这个叶子对应了一个ascll码值
				{
					str[i] = k + 'a';
				}
			}
			break;
		}
	}
	for (i = 0; i < m; i++)
	{
		if (arr[1] == HFtree[i].weight && i != *x && HFtree[i].parent == 0)//找到第二小的无双亲的树
		{
			*y = i;
			int k = 0;
			for (k = 0; k < 26; k++)
			{
				if (count[k] == HFtree[i].weight)
				{
					str[i] = k + 'a';
				}
			}
			break;
		}
	}
}

//创建哈夫曼树
void HFtree_Build(HuffmanTree HFtree,int n,char* str, int* count)
{
	int i = 0;
	int m = n * 2 - 1;
	int x = 0;
	int y = 0;
	for (i = n; i < m; i++)
	{
		Str_Sort(HFtree, n, &x, &y,str,count);
		HFtree[i].lchild = x;//左边孩子最小，右边孩子第二小
		HFtree[i].rchild = y;
		HFtree[i].weight = HFtree[x].weight + HFtree[y].weight;
		HFtree[x].parent = i;
		HFtree[y].parent = i;
		x = 0;
		y = 0;
	}
}

//对哈夫曼树进行编码
void HFtree_Code(HuffmanTree HFtree,int num,char**arr)
{
	int i = 0;
	for (i = 0; i < num; i++)
	{
		int a = i;
		int j = 0;
		while (HFtree[a].parent != 0)//从叶子一直往祖先寻
		{
			if (HFtree[HFtree[a].parent].lchild == a)//如果当前节点是双亲节点的左孩子
			{
				arr[i][j] = '0';
			}
			else if (HFtree[HFtree[a].parent].rchild == a)//如果当前节点是双亲节点的右孩子
			{
				arr[i][j] = '1';
			}
			a = HFtree[a].parent;
			j++;
		}
	}
}

//哈夫曼编码解码
//s是编码结果数组，a是存储的字符串数组
void HuffmanDeCode(HuffmanTree HT, char* s, char a[], int n) 
{
	int i = 0;
	int f = 2 * n - 1 - 1;
	while (s[i] != '\0')
	{
		if (s[i] == '0')
			f = HT[f].lchild;
		else
			f = HT[f].rchild;
		if (f < n)
		{
			printf("%c", a[f]);
			f = 2 * n - 1 - 1;
		}
		i++;
	}
	printf("\n");
}